\documentclass{article}
%\usepackage{fullpage}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}
\usepackage[utf8x]{inputenc}

\lstdefinelanguage{TRIO}
	{morekeywords={class, temporal, domain, visible, TD, items, TI, variable, const, predicate, modules, axioms, end},
	morecomment=[l][\itshape]{--}
	}

\begin{document}
\begin{titlepage}
\begin{center}
\vspace*{1cm}
\large
  POLITECNICO DI MILANO\\
  \normalsize
  Corso di Laurea Specialistica in Ingegneria Informatica\\
  Dipartimento di Elettronica e Informazione\\
  \begin{figure}[htbp]
    \begin{center}
      \includegraphics[width=3.5cm]{logopm}
    \end{center}
  \end{figure}
  \vspace*{2cm}
\textsc{\Large Progetto Algoritmi e Architetture per Sistemi Crittografici}\\[2cm]
\rule{\linewidth}{0.5mm} \\[0.4cm]
{ \huge \bfseries CUDA MD5 Breaker}\\[0.4cm]
\rule{\linewidth}{0.5mm} \\[2.5cm]
\begin{flushleft} \large
Valerio \textsc{Ponte} - \emph{valerio.ponte@gmail.com}\\
Ermes \textsc{Viviani} - \emph{ermesviviani@gmail.com}
\end{flushleft}
\vfill
% Bottom of the page
{\large \today}
\end{center}
\end{titlepage}

\section*{Obiettivo}
L'obiettivo del progetto è la realizzazione di uno strumento software in grado di eseguire attacchi a forza bruta o a dizionario a delle password di sistema *nix. In particolare il progetto intende sfruttare le potenzialità di calcolo parallelo offerte dai moderni processori grafici, in modo da ottenere prestazioni migliori rispetto ad un breaker tradizionale che sfrutti solo la CPU. Il breaker realizzato nell'ambito del progetto rompe password crittografate per mezzo dell'algoritmo MD5.

\section*{Implementazione}
I due possibili linguaggi di programmazione per sviluppare il progetto erano OpenCL e CUDA. Poiché il progetto mirava ad ottenere dei forti guadagni in termini di prestazioni e c'era la possibilità di utilizzare delle schede video Nvidia, la scelta è caduta su CUDA. Questo anche perchè non avevamo precedenti conoscenze di nessuno dei due linguaggi ed essendo CUDA specifico per schede Nvidia, ci aspettavamo delle prestazioni migliori.

L'idea di base è stata quella di reimplementare in CUDA la funzione delle librerie glibc \textit{crypt} nella sua variante che utilizza MD5. La funzione di calcolo di MD5 è stata anch'essa reimplementata a partire dalla stessa fonte. Com'è noto la funzione crypt calcola l'hash di una stringa in ingresso. Per far sì che il breaker funzioni è necessario un meccanismo di generazione degli input. Per il progetto sono stati realizzati due approcci classici:
\begin{description}
	\item[dizionario] Il breaker legge un file specificato dall'utente contenente una lista di parole, e per ognuna ne calcola l'hash, confrontando il risultato con l'hash obiettivo. In questa modalità il dizionario viene caricato nella memoria globale della GPU e i diversi thread ne analizzano parti diverse, interrompendosi qualora la password corrispondente all'hash obiettivo sia stata trovata. Supponendo di avere un dizionario di lunghezza $n$ password e di lavorare con $m$ thread, ogni thread analizzerà in media $n/m$ password: il thread $i$ analizza le password da $i\times n/m$ fino a $((i+1)\times n/m)-1$.
	\item[brute force] Il breaker genera una serie di stringhe utilizzando un alfabeto ed una lunghezza di parola specificati dall'utente, e per ognugna di queste ne calcola l'hash, confrontandolo con l'hash obiettivo. Le stringhe generate sono tutte le possibili permutazioni di lunghezza data sull'alfabeto. L'alfabeto viene caricato nella memoria locale di ogni thread, che, in base al proprio indice e alla quantità di password possibili (calcolata come $|\Sigma|^{len}$, dove $\Sigma$ indica l'alfabeto e $len$ la lunghezza delle password) genera ed analizza una sequenza di password: sia $i$ l'indice del thread, $n$ la quantità di password totali e $m$ il numero di thread, il thread $i$ genera ed analizza $n/m$ password come nel caso precedente. Poiché è possibile associare biunivocamente ad un numero $j$ una password sull'alfabeto $\Sigma$, è possibile, partendo da $j$ generare la password corrispondente. Questo principio viene utilizzato da ogni thread per generare le password che gli competono.
\end{description}
Per hash obiettivo si intende un hash in formato esadecimale fornito in ingresso dall'utente. Una volta generata una password, il calcolo del relativo hash MD5 viene effettuato localmente rispetto ad ogni thread, così come il confronto con l'hash obiettivo. Nel caso in cui un thread trovi l'hash obiettivo l'esecuzione di tutti i thread viene fermata e il programma termina.

\section*{Utilizzo}
Avendo a disposizione il programma compilato, è sufficiente invocarlo da linea di comando nel modo seguente:

\begin{verbatim}
./md5_breaker [ -m mode ] [ -j jobs ] [ -d dictionary_path ]
              [ -s salt ] [ -i target_hash ] [ -l password_length ]
\end{verbatim}
In cui:
\begin{description}
	\item[mode] Indica la modalità di generazione delle password: 0 per la modalità dizionario, 1 per la modalità brute force (deafult: 0).
	\item[jobs] Indica il numero di thread da utilizzare (default: 1).
	\item[dictionary\_path] Indica il file contenente il dizionario da utilizzare in modalità 0. Se non indicato il programma termina immediatamente indicando l'assenza di un file appropriato.
	\item[salt] Indica la stringa di sale crittografico (default: "").
	\item[target\_hash] Indica l'hash obiettivo, espresso come una stringa esadecimale (default: tutti 0).
	\item[password\_length] Indica la lunghezza delle password generate in modalità 1 (default: 4).
\end{description}
Il dizionario deve essere composto da una serie di parole terminate ciascuna da un \textit{carriage return}.

\section*{Risultati}
\phantom{Fa schifo, gli altri sono molto meglio.}
Sul programma realizzato sono stati effettuati dei testi al fine di misurarne le prestazioni. La macchina utilizzata per il testing era equipaggiata come segue:
\begin{description}
	\item[CPU] Intel I7 920 @2.67 GHz
	\item[RAM] $\sim$ 12 GB
	\item[GPU] GeForce GTX 470 con 1267 MB di RAM
	\item[Nvidia driver] v275.09.07
	\item[CUDA Toolkit] v4.0.17
	\item[SO] Gentoo Linux 2.6.39
\end{description}

I test svolti sono stati due, uno per testare la modalità dizionario, usando un dizionario di 3169 parole, ed uno per testare la modalità a forza bruta, utilizzando l'alfabeto $\Sigma = \{a, b, c, d, e, f, g, h\}$ con password di lunghezza 5.

\begin{figure}
\begin{minipage}[b]{0.5\textwidth}
\centering
\includegraphics[width = \textwidth]{words_time.png}
\caption{Tempo di analisi di un dizionario di 3169 parole.}
\label{fig:words_time}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\textwidth}
\centering
\includegraphics[width = \textwidth]{force_time.png}
\caption{Tempo di analisi a forza bruta su 32768 parole.}
\label{fig:force_time}
\end{minipage}
\end{figure}

\begin{figure}
\begin{minipage}[b]{0.5\textwidth}
\centering
\includegraphics[width = \textwidth]{words_hash.png}
\caption{Password analizzate al secondo di un dizionario di 3169 parole.}
\label{fig:words_hash}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\textwidth}
\centering
\includegraphics[width = \textwidth]{force_hash.png}
\caption{Password analizzate al secondo a forza bruta su 32768 parole.}
\label{fig:force_hash}
\end{minipage}
\end{figure}

I risultati degli esperimenti sono mostrati nelle figure \ref{fig:words_time}, \ref{fig:force_time}, \ref{fig:words_hash} e \ref{fig:force_hash}. Come si può vedere, il breaker realizzato mostra una buona scalabilità in termini di numero di thread utilizzati. Per limitazioni del toolkit CUDA, sulle schede video attuali non è possibile lanciare più di 512 thread su un singolo blocco. Per questo motivo i test effettuati con numero di thread maggiore di 512 sono stati eseguiti mappando i thread su diversi blocchi.

Si può vedere come la modalità a forza bruta sia molto più performante rispetto alla modalità a dizionario. Una probabile causa di ciò può essere individuata nel fatto che la modalità dizionario impiega molta più memoria globale della scheda video poiché il dizionario è ivi memorizzato e ogni thread deve accedervi per ogni password.

Il termine di paragone utilizzato per misurare le prestazioni del breaker realizzato è stato \textit{John the Ripper}, breaker open source che utilizza solo la CPU. E' evidente pertanto che, essendo il processore invariato, le prestazioni di John the Ripper sono rimaste invariate; queste si sono attestate attorno alle 11500 password al secondo. E' quindi evidente che il breaker realizzato, nonostante minori prestazioni nella modalità dizionario, può comunque considerarsi una valida alternativa per la modalità a forza bruta.

\end{document}
